动态规划
定义
动态规划与分治法相似，都是通过组合子问题的解来求解原问题答案，将问题划分为互不相交的子问题，递归的求解子问题，最后合并子问题的答案，得到原问题的答案。
示例
斐波那契数列
之前的斐波那契数列使用递归法快速易懂，但是在时间和空间的使用效率上，还有待提高。
在动态规划的思想里，我们可以使用 dp 列表，来记录所有斐波那契数列的值，从而减少递归，提升运行效率。
python
n = int(input())
dp = [0]*n
dp[1] = dp[2] = 1
for i in range(3,n):
dp[i] = dp[i - 1] + dp[i - 2]
print(dp[n])参考资料知乎：动态规划
总结
所以总结一下，要想解决一个动态规划问题，下面的三要素是必须的：
- 最优子结构，上文提到的拆分到的最小的那一步。
- 边界 ，涉及到递归必须考虑的问题。
- 状态转移方程 ，拆分过程中不同步之间的关系。
之前贪心算法中讲到的跳跃游戏也算使用到了动态规划的思想。